#include<stdio.h>

int main()
{
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	int n,i,x,j,h=1,b[60];
	long long a[60];
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
	}
	for (i=1;i<=n;i++)
	{
		a[0]=1;
		a[1]=1;
		a[2]=1;
		if (b[i]==0||b[i]==1||b[i]==2)
			printf("%d\n",h);
		else
		{
			for (j=3;j<=b[i];j++)
				a[j]=a[j-1]-2*a[j-2]+3*a[j-3];
			printf("%lld\n",a[b[i]]);
		}
	}
	return 0;
}
